perm filename RLISP.ACH[UP,DOC]3 blob
sn#245542 filedate 1976-11-06 generic text, type T, neo UTF8
UTAH COMPUTATIONAL PHYSICS GROUP October 1974
OPERATING NOTE NO. 5.1
R E D U C E 2
S Y M B O L I C M O D E
P R I M E R*
by
Anthony C. Hearn
University of Utah
*Work supported in part by the National Science Foundation under
Grant No. GJ-32181 and by the Advanced Research Projects Agency of
the Office of the Department of Defense under Contract No.
DAHC15-73-C-0363.
2
1. INTRODUCTION
REDUCE is a program designed primarily for general algebraic
computations of interest to mathematicians, physicists and engineers.
However, its source language is general enough to allow for a full
range of LISP-like symbolic calculations. This primer is a brief
guide to this source language. It does not describe the algebraic
capabilities of the system, so anyone interested in these should
consult the REDUCE 2 User's Manual [1], of which this primer is an
extract.
This primer assumes that the reader has a reasonable
acquaintance with LISP 1.5 at the level of the LISP 1.5 Programmer's
Manual [2] or Clark Weissman's LISP 1.5 Primer[3]. Anyone unfamiliar
with this material is advised to study it before proceeding further.
In Section 2 of this primer, we give details of the basic
structure of REDUCE programs. In Section 3, a list of the functions
available in the system is given, and finally in Section 4 a syntax
definition of a subset of REDUCE is given.
The author would appreciate hearing from any users who
experience trouble with the system (please include copies of relevant
input and output).
3
2. STRUCTURE OF PROGRAMS
2.1 Preliminary
A REDUCE program consists of a set of functional commands
which are evaluated sequentially by the computer. These commands are
built up from declarations, statements and expressions. Such
entities are composed of sequences of numbers, variables, operators,
strings, reserved words and delimiters (such as commas and
parentheses), which in turn are sequences of basic characters.
2.2 The REDUCE Standard Character Set
The basic characters which are used to build up REDUCE symbols are
the following:
i) The 26 upper case letters A through Z
ii) The 10 decimal digits 0 through 9
iii) The special characters ! " $ % ' ( ) * + , - . / : ; < > = <blank>
Programs composed from this standard set of characters will run in
any available REDUCE system. In addition, several implementations of
REDUCE (for example, on the PDP-10) use additional characters to
represent some of the operators in the system. The local operating
instructions for the given computer should be consulted for the
meaning of these special characters. However, for generality in
exposition we shall limit ourselves to the standard character set in
the body of this manual.
2.3 Numbers
Numbers in REDUCE may be of two types; integer and real.
Integers consist of a signed or unsigned sequence of decimal digits
written without a decimal point.
e. g. -2, 5396, +32
Real numbers may be written in two ways;
i) as a signed or unsigned sequence of 1-9 decimal digits with
an embedded decimal point.
ii) as in i) followed by a decimal exponent which is written as
the letter E followed by a signed or unsigned integer.
e. g. 32. +32.0 0.32E2 and 320.E-1 are all representations of 32.
Restriction:
The unsigned part of any number may NOT begin with a decimal point.
4
i. e. NOT ALLOWED .5 -.23 +.12
2.4 Identifiers
Identifiers in REDUCE consist of one to twenty-four
alphanumeric characters (i.e. upper case alphabetic letters or
decimal digits) the first of which must be alphabetic.
e. g. A AZ P1 Q23P AVERYLONGVARIABLE
It is also possible to include non-alphanumeric characters in
identifiers by prefixing the character by an exclamation mark.
e. g., DSK!: GET!*!* A!+B
Identifiers are used as variables, labels and to name operators,
arrays and procedures.
Restrictions:
Reserved words in REDUCE (see Section 2.10) may not be used as
identifiers. No spaces may appear within an identifier, and an
identifier may not extend over a line of text.
2.5 Variables
Variables are a particular type of identifier, and are
specified by name and type. Their names must be allowed
identifiers. There are several variable types allowed, and these
are discussed later in Section 2.12.1.
2.6 Operators
Operators in REDUCE are also specified by name and type.
There are two types, infix and prefix.
Infix operators occur between their arguments.
e. g. A + B - C
U . V
The following infix operators are built into the system.
<infix operator> ::= :=|OR|AND|NOT|MEMBER|=|NEQ|EQ|>=|>|<=|<|+|-|*|/|**|.
These operators may be further divided into the following sub
classes
<assignment operator> ::= :=
<logical operator> ::= OR|AND|NOT|MEMBER
<relational operator> ::= =|EQ|NEQ|>=|>|<=|<
5
<arithmetic operator> ::= +|-|*|/|**
<symbolic operator> ::= .
For compatibility with the intermediate language used by
REDUCE, each special character infix operator has an additional
alphanumeric identifier associated with it. These identifiers may
be used interchangably with the corresponding infix character(s) on
input. This correspondence is as follows:
:= SETQ
= EQUAL
>= GEQ
> GREATERP
<= LEQ
< LESSP
+ PLUS
- DIFFERENCE (unary MINUS)
* TIMES
/ QUOTIENT (unary RECIP)
** EXPT
. CONS
The above operators are assumed to be binary, except NOT which is
unary and + and * which are nary. In addition, - and / may be used in
a unary position. Any other operator is parsed as a binary operator
using a left procedure grouping. Thus A/B/C is interpreted as
(A/B)/C. There are two exceptions to this latter rule, namely := and
. which have a right precedence grouping. Thus A . B . C is
interpreted as A . (B . C).
Parentheses may be used to specify the order of combination. If
parentheses are omitted then this order is by the precedence ordering
given by the above list. I. e., := has the lowest precedence and .
the highest.
Prefix operators occur at the head of their arguments, which
are written as a list enclosed in parentheses and separated by
commas, as with normal mathematical functions.
e. g. CAR(U)
RPLACD(U,LIST(V))
Parentheses may be omitted if the operator is unary.
e. g. CAR Y and CAR(Y) are equivalent.
Such unary prefix operators have a precedence higher than any infix
operator.
Infix operators may also be used in a prefix format on input.
On output, however, they will always be printed in infix form.
6
2.7 Strings
Strings are used only in output statements. A string consists
of any number of characters enclosed in double quotes.
e. g. "A STRING"
2.8 Comments
Comments are useful for including explanatory material at
various points in a program. They may be used in the following form:
COMMENT <any sequence of characters not including a terminator>
<terminator>
where
<terminator> ::= ;|$
e. g. COMMENT THIS IS A COMMENT;
In addition, the sequence of symbols
END <any sequence of symbols not including a terminator, a right
parenthesis or the reserved words END, ELSE or UNTIL>
is equivalent to the reserved word END.
2.9 Expressions
REDUCE expressions may be of several types and consist of
syntactically allowed sequences of numbers, variables, operators,
left and right parentheses and commas. The most common types are as
follows:
2.9.1 Numerical Expressions
These consist of syntactically allowed combinations of
integer or real variables, arithmetic operators and parentheses, and
evaluate to numbers.
Examples:
2
I + J - 2 * I**2
are numerical expressions if I and J are integers.
2.9.2 Boolean Expressions
These are expressions which return a truth value. In REDUCE,
the reserved word NIL represent the truth value 'false'. Any other
expression represents 'true'. So in a sense, any expression is a
7
boolean expression, because all expressions return a value. However,
a proper boolean expression has the syntactical form:
<expression> <relational operator> <expression>
or
<boolean expression> <logical operator> <boolean expression>
or
NIL|T
They are used mainly in the IF and FOR statements described in
Sections 2.12.2 and 2.12.3.
Examples:
J<1
3*X-1 >2
U MEMBER V OR X=Y
2.9.3 Symbolic Expressions
These consist of scalar variables and operators and follow
the normal rules of the LISP meta language.
Examples:
X
CAR U . REVERSE V
CDR(IF X=Y THEN X ELSE U)
2.9.4 Quoted Expressions
Because LISP evaluation requires that each variable or
expression have a value, it is necessary to add to REDUCE the concept
of a quoted expression by analogy with the LISP QUOTE function. This
is provided by the single quote mark '.
e. g. 'A represents the LISP S-expression (QUOTE A)
'(A B C) represents the LISP S-expression (QUOTE (A B C))
Within a quoted expression, identifier syntax rules are those of
REDUCE. Thus (A !. B) is the list consisting of the three elements A,
. and B, whereas (A . B) is the dotted pair of A and B.
2.9.5 LAMBDA Expressions
LAMBDA expressions provide the means for constructing LISP
LAMBDA expressions.
8
Syntax:
<LAMBDA expression> ::= LAMBDA <varlist><terminator><statement>
<varlist> ::= (<variable>,...,<variable>)
e. g. LAMBDA (X,Y); CAR X . CDR Y
is equivalent to the LISP LAMBDA expression
(LAMBDA (X Y) (CONS (CAR X) (CDR Y)))
The parentheses may be omitted in specifying the variable
list if desired.
LAMBDA expressions may be used in symbolic mode in place of
prefix operators, or as an argument of the reserved word FUNCTION.
2.10 Reserved Words
Certain words are reserved in REDUCE. They may only be used
in the manner described in this Manual. In particular, all the infix
operators introduced in Section 2.6 are of this type, plus the
statement and command names and other identifiers in the following
list:
<reserved word> ::= BEGIN|DO|ELSE|END|FOR|FUNCTION|GO|GOTO|IF|LAMBDA|
T|NIL|PRODUCT|RETURN|STEP|SUM|TO|UNTIL|WHILE|
IN|OUT|ON|OFF|SHUT|WRITE
2.11 Statements
A statement is any allowed combination of reserved words and
expressions, and has the syntax
<statement> ::= <expression>|<proper statement>
The following are some proper statements in REDUCE:
2.11.1 Assignment Statements
These statements have the following syntax
<assignment statement> ::= <expression> := <statement>
In symbolic mode, if the left side of an assignment statement
is a variable, a SETQ of the right hand side to that variable occurs.
e. g. X:=Y translates into (SETQ X Y).
It is also possible to write an assignment in the form
9
<expression> := <expression> := ... := <expression> := <statement>
In this form, each <expression> is set to the value of the <statement>
by the right precedence grouping described in Section 2.6.
2.11.2 Conditional Statements
The conditional statement has the following syntax:
<conditional statement> ::= IF <boolean expression> THEN <statement>
ELSE <statement>
Its use is obvious. The ELSE clause is optional.
Conditional statements associate to the right; i.e.,
IF <a> THEN <b> ELSE IF <c> THEN <d> ELSE <e>
is equivalent to:
IF <a> THEN <b> ELSE (IF <c> THEN <d> ELSE <e>)
In addition, the construction
IF <a> THEN IF <b> THEN <c> ELSE <d>
parses as
IF <a> THEN (IF <b> THEN <c> ELSE <d>)
2.11.3 FOR Statements
The FOR statement is used to define a program loop. Its
syntax is as follows:
FOR <variable>:=<arithmetic expression> STEP <arithmetic expression>
UNTIL <arithmetic expression> DO <statement>
The FOR statement follows the normal ALGOL usage. It returns
the value NIL.
2.11.4 WHILE Statements
This statement also defines a program loop. Its syntax is as
follows:
WHILE <boolean statement> DO <statement>
The <boolean statement> is first tested. If true, the
<statement> is executed and the process then repeated until the
<boolean statement> is false.
10
2.11.5 GO TO Statements
GO TO (or GOTO) statements are used to perform an
unconditional transfer to a label in a compound statement (Section
2.11.6). They have the syntax:
<go to statement> ::= GO TO <label>
<label> ::= <variable>
Restrictions:
GO TO statements may only occur within a compound statement. They may
NOT occur at the top level of your program. Furthermore, they can
only reference labels within the local block in which they are
defined.
2.11.6 Compound Statements
A compound statement is defined by the following syntax
<compound statement> ::= BEGIN <compound tail>
<compound tail> ::= <unlabeled compound tail>
|<label>:<compound tail>
<unlabeled compound tail> ::= <statement> END
| <statement> <terminator> <compound tail>
<label> ::= <identifier>
<terminator> ::= ;|$
e. g. X := BEGIN INTEGER M;
M:=1;
L1: IF N=0 THEN RETURN M;
M:=M*N;
N:=N-1;
GO TO L1
END OF BLOCK
will assign the factorial of a preassigned non-negative integer N to X.
2.11.7 RETURN Statements
The RETURN statement allows for a transfer out of a compound
statement to the next highest program level. It may be used alone,
in which case the statement returns NIL.
e. g., RETURN X+Y
RETURN M
RETURN
Restriction:
RETURN statements may only occur within a compound statement.They may
NOT occur at the top level of your program.
11
2.12 Declarations
Declarations are a particular type of statement used to set
flags, make type declarations and define procedures. PROCEDURE
declarations are discussed in Section 2.15. Some other REDUCE
declarations are as follows:
2.12.1 Variable Type Declarations
These declarations tell the system how various identifiers
are to be processed. Types allowed include INTEGER, REAL and SCALAR.
e. g. INTEGER M,N
REAL M1
SCALAR X,Y
Type declarations may be made at any level in a program, and apply
only to the particular program block in which they occur. They MUST
however immediately follow the BEGIN key-word if they are declared
within a block. Variables not declared are assumed SCALAR. This is
the basic algebraic variable type.
2.12.2 Array declarations
Arrays in REDUCE are defined similar to FORTRAN dimension
statements.
e. g. ARRAY A(10),B(2,3,4)
Their indices each range from 0 to the value declared. An element of
an array is referred to in standard FORTRAN notation,
e. g. A(2)
All array elements are initialized to 0 at declaration time.
Array elements may appear in the left side of assignment statements.
2.12.3 Mode Handling Declarations
Two declarations are offered to the user for turning on or
off a variety of flags in the system. The declarations ON and OFF
take a list of flag names as argument and turn them on and off
respectively.
e. g. ON ECHO
OFF INT
The use of these flags and others available to the user is
explained later in this manual.
12
2.13 Commands
A command is an order to the system to do something. It has
the syntax
<command> ::= <statement><terminator>|<proper command>
<proper command> ::= <command name><space>
<statement>,...,<statement><terminator>
A variety of commands are discussed in the sections which follow.
2.14 File Handling Commands
In many applications, it is desirable to load previously
prepared REDUCE files into the system, or to write output on varying
devices. REDUCE offers three commands for this purpose, namely, IN,
OUT, and SHUT.
2.14.1 IN
This command takes a list of file names as argument and
directs the system to input each file (which should contain REDUCE
commands) into the system. A file name will have a varying syntax
from implementation to implementation, but in many cases will be an
identifier.
e. g. IN F1,GGG; will load the files F1 and GGG.
When input comes from an external file, statements are echoed
on the output device as they are read. If this facility is not
required, the echoing can be prevented by turning off the flag ECHO
in the relevant file.
2.14.2 OUT
This command takes a single file name as argument, and
directs output to that file from then on. If the file has previously
been used for output during the current job, the output is appended
to the end of the file. An existing file is erased before its first
use for output in a job.
To output on the terminal without closing the output file,
the reserved file name T (for terminal) may be used.
e. g. OUT OFILE; will direct output to the file OFILE and
OUT T; will direct output the user's terminal.
13
2.14.3 SHUT
This command is used to close an output file at completion.
Most systems require this action by the user, otherwise output may be
lost. If a file is shut and a further OUT command issued for the
same file, the file is erased before the new output is written.
2.15 Procedures
It is often useful to name a statement for repeated use in
calculations with varying parameters, or to define operators.
REDUCE offers a procedural declaration for this purpose. Its general
syntax is:
<procedural type> PROCEDURE <name><varlist>;<statement>;
with
<varlist> ::= <empty>|(<variable>,...,<variable>)
or
<procedural type>
PROCEDURE <variable> <binary infix name> <variable>;
<statement>;
The types permitted are REAL, INTEGER, SYMBOLIC, FEXPR and MACRO.
E. g., the example in Section 2.11.6 could be made into an integer
procedure FAC by the declaration:
INTEGER PROCEDURE FAC (N);
BEGIN INTEGER M;
M:=1;
L1: IF N=0 THEN RETURN M;
M:=M*N;
N:=N-1;
GO TO L1
END;
If we now evaluate FAC (3) we get the result 6.
LISP function definitions may also be input in a procedural
form. The procedural type in this case is SYMBOLIC. For example, we
can define an association list searching function ASSOC as follows:
SYMBOLIC PROCEDURE ASSOC(U,V);
IF NULL V THEN NIL
ELSE IF U=CAAR V THEN CAR V
ELSE ASSOC (U,CDR V);
FEXPRs and MACROS may also be input in this manner with the
procedural types FEXPR and MACRO respectively.
14
In order to allow users relatively easy access to the whole
REDUCE source program, system procedures are not protected against
user redefinition. If a procedure is redefined, a message
*** <procedure name> REDEFINED
is printed. If this occurs, and the user is not redefining his own
procedure, he is well advised to rename it!
2.16 Output of Strings
It is often useful to write a title or comment on output, or
name output expressions in a particular way. This is possible in
REDUCE by means of the command WRITE. The form of this command is
WRITE <expression>,...,<expression>;
where <expression> may be either a symbolic expression or a string
(Section 2.7). Strings are printed on output exactly as given except
for any characters which are ignored by the input scanner. Other
expressions are evaluated and their value printed.
The print line is closed at the end of the WRITE command
evaluation.
2.17 Commands Used in Interactive Systems
REDUCE is designed primarily for interactive use with a time-
shared computer, but naturally it can also operate in a batch
processing environment. There is a basic difference, however,
between interactive and batch use of the system. In the former case,
whenever the system discovers an ambiguity at some point in a
calculation, such as a forgotten type assignment for instance, it
asks the user for the correct interpretation. In batch operation, it
is not practical to terminate the calculation at such points and
require resubmission of the job, so the system makes the most obvious
guess of the user's intentions and continues the calculation.
If input is coming from an external file, the system treats
it as a batch processed calculation. If the user desires interactive
response in this case, he can turn on the flag INT in the file.
Likewise, he can turn off INT in the main program if he does not
desire continual questioning from the system.
Two commands are available in REDUCE for use in interactive
computing. The command PAUSE; may be inserted at any point in an
input file. When this command is encountered on input, the system
prints the message CONT? on the user's terminal and halts. If the
user responds Y (for yes), the calculation continues from that point
in the file. On the other hand, if the user responds N (for no),
control is returned to the terminal, and the user can input further
commands. However, later on he can use the command CONT;, and control
15
is then transferred back to the point in the file after the last
PAUSE was encountered.
2.18 END
The command END; is used to end external files which are used
as input to REDUCE. One of its purposes is to turn off the command
echo, which is annoying to a user typing at a terminal. However, it
also does some file control book-keeping (for example, any files
still open are automatically closed), and should therefore not be
omitted.
If an END command is used in the main program, control is
then transferred to LISP.
16
3. FUNCTIONS DEFINED IN REDUCE
This Section gives the definitions of some of the functions
available in REDUCE. The list is not complete; for example, it omits
all functions concerned with the scanning and parsing of input. The
definitions of the latter functions may be found by examining the
source of REDUCE.
The definitions are divided into two main groups. First are
those functions which must be implemented at the machine or assembly
language level. The second group are those which can be defined in
terms of the basic set. In the latter case, the complete REDUCE
definition is included.
3.1 BASIC REDUCE FUNCTIONS
3.1.1 General Functions
%SYMBOLIC PROCEDURE ATOM(U);
%Returns T if U is an atom, NIL otherwise;
%SYMBOLIC PROCEDURE CAR(U);
%Returns first half of dotted pair U. Undefined for atoms;
%SYMBOLIC PROCEDURE CDR(U);
%Returns second half of dotted pair U. Undefined for atoms;
%SYMBOLIC PROCEDURE COMPRESS(U);
%Creates an atom (literal atom or number) from list of characters U,
%adds it to the OBLIST if one exists, and returns the atom;
%SYMBOLIC PROCEDURE CONS(U,V);
%Reclaims a free cell from the free storage list (or first calls the
%garbage collector if the free storage list is empty).
%Returns the dotted pair of U and V as a pointer to the new cell;
%SYMBOLIC PROCEDURE EQ(U,V);
%Returns T if U and V are identical objects (i.e., U and V point
%to the same location), NIL otherwise.
%SYMBOLIC PROCEDURE ERROR(U);
%Causes an error diagnostic to occur. The argument U is printed
%and control then returns to the top level read-eval-print loop;
%SYMBOLIC PROCEDURE ERRORSET(U,V);
%If an error occurs during the evaluation of U, NIL is returned. The
%error message is printed if and only if V is T. If no error occurs,
%LIST (!*EVAL(U)) is returned;
%SYMBOLIC PROCEDURE EXPLODE(U);
%Returns a list of the constituent characters of atom U. Must also
%work for integers. E.g., EXPLODE 123 = (1 2 3);
17
%FEXPR PROCEDURE FUNCTION(U);
%Used with constant functional arguments;
%SYMBOLIC PROCEDURE GENSYM();
%Creates a new atom (e.g., G0123), adds it to the OBLIST if one
%exists, and returns the atom;
%SYMBOLIC PROCEDURE GETD(U);
%Returns pointer to definition of U, if U is a function or MACRO,
%and NIL otherwise;
%FEXPR PROCEDURE GO(U);
%Causes a transfer to label U;
%SYMBOLIC PROCEDURE ORDERP(U,V);
aaa%Used to test the order of objects according to their location.
%Returns T if U is ordered ahead of, or equal to V, NIL otherwise;
%SYMBOLIC PROCEDURE PUTD(NAME,VARLIS,BODY,TYPE);
%Creates a function NAME, with variable list VARLIS and definition
%BODY. TYPE is EXPR, FEXPR, or MACRO;
%SYMBOLIC PROCEDURE RETURN(U);
%Causes return from a compound statement with value U;
%SYMBOLIC PROCEDURE RPLACA(U,V);
%U is a non-atomic S-expression, V an S-expression. RPLACA
%stores V in the CAR field of U and returns the modified U;
%SYMBOLIC PROCEDURE RPLACD(U,V);
%U is a non-atomic S-expression, V an S-expression. RPLACD
%stores V in the CDR field of U and returns the modified U;
%SYMBOLIC PROCEDURE STRINGP(U);
%Returns T if U is a string, NIL otherwise;
3.1.2 Functions for Input and Output
%FEXPR PROCEDURE COMMENT(U);
%Reads in the string U and acts like a <blank> to the scanner;
%SYMBOLIC PROCEDURE DIGIT(U);
%Returns T if U is one of the digits 0 thru 9, NIL otherwise;
%SYMBOLIC PROCEDURE LITER(U);
%Returns T if U is one of the letters A thru Z, NIL otherwise;
%SYMBOLIC PROCEDURE PRINC(U);
%Adds the character string U to the output buffer. Does not close
%the print line. Returns U;
18
%SYMBOLIC PROCEDURE PRIN1(U);
%Adds the character string U to the output buffer, prefixing any
%special characters with an escape character. Does not close the
%print line. Returns U;
%SYMBOLIC PROCEDURE READCH();
%Reads and returns one character from the input buffer;
%SYMBOLIC PROCEDURE TERPRI();
%Prints the current contents of the output buffer and ends with an
%EOR. Prints a blank line if the buffer is empty;
3.1.3 Property List Functions
%SYMBOLIC PROCEDURE FLAG(U,V);
%U is a list of literal atoms and V a literal atom.
%Puts the flag V on the property list of each member of U;
%SYMBOLIC PROCEDURE FLAGP(U,V);
%Returns T if the atom U has flag V on its property list, otherwise
%NIL;
%SYMBOLIC PROCEDURE GET(U,V);
%U is a literal atom (not a number!).
%Value is the property of U whose indicator is V (or NIL if
%indicator not present);
%SYMBOLIC PROCEDURE PUT(U,IND,PROP);
%U and IND are literal atoms, PROP an S-expression.
%Puts PROP on property list of U with indicator IND;
%SYMBOLIC PROCEDURE REMPROP(U,V);
%U and V are literal atoms.
%Removes property with indicator V from property list of U;
%SYMBOLIC PROCEDURE REMFLAG(U,V);
%Removes the flag V from the property list of each member of U;
3.1.4 Arithmetic Functions
%SYMBOLIC PROCEDURE M**N;
%M and N are integers or floating point numbers. Value is M**N;
%SYMBOLIC PROCEDURE FIX M;
%Returns integer part of number M;
%SYMBOLIC PROCEDURE FIXP M;
%Returns T is M is an integer, NIL otherwise;
%SYMBOLIC PROCEDURE M<N;
%M and N are numbers. Returns T if M<N, NIL otherwise;
19
%SYMBOLIC PROCEDURE -M;
%Returns negative of number M;
%SYMBOLIC PROCEDURE NUMBERP M;
%Value is T if M is a number, NIL otherwise;
%SYMBOLIC PROCEDURE M+N;
%Returns sum of numbers M and N;
%SYMBOLIC PROCEDURE M/N;
%Returns quotient of numbers M and N;
%SYMBOLIC PROCEDURE /M;
%Returns reciprocal of number M;
%SYMBOLIC PROCEDURE REMAINDER(M,N);
%Returns remainder on dividing integer M by integer N;
%SYMBOLIC PROCEDURE M*N;
%Returns product of numbers M and N;
3.1.5 Array Handling Functions
%SYMBOLIC PROCEDURE ARRAY(U);
%Initializes arrays. Same definition as for SHARE LISP except that
%'LIST' is omitted;
%SYMBOLIC PROCEDURE GETEL(U);
%Returns array element U;
%SYMBOLIC PROCEDURE SETEL(U,V);
%Sets array element U to V. Returns V;
3.1.6 File Handling Functions
%SYMBOLIC PROCEDURE CLOSE(FILE);
%Closes FILE by writing appropriate end-of-file marks, etc.
%Returns FILE;
%SYMBOLIC PROCEDURE OPEN(FILE,STAT);
%Opens a file named FILE on some external device. STAT = INPUT or
%OUTPUT. Returns FILE;
%SYMBOLIC PROCEDURE RDS(FILE);
%Selects FILE as input device. All input now comes from FILE. If
%FILE is NIL, then the standard input device is selected. Returns
%previous input file;
%SYMBOLIC PROCEDURE WRS(FILE);
%Selects FILE as output device. All output now goes to FILE. If FILE
%is NIL, then the standard output device is selected. Returns prev-
%ious input file;
20
3.1.7 Interpreter Functions
%SYMBOLIC PROCEDURE !*EVAL(U);
%Evaluates expression U and returns value. If U is a special atom,
%its special value is returned;
%SYMBOLIC PROCEDURE GTS(U);
%Returns ('gets') the value of the special atom U;
%SYMBOLIC PROCEDURE PTS(U,V);
%U is declared special if not already. PTS gives U the special value
%V and returns V;
21
3.2 COMPOSITE REDUCE FUNCTIONS
SYMBOLIC PROCEDURE ABS M;
IF M<0 THEN -M ELSE M;
FEXPR PROCEDURE AND U;
BEGIN
A: IF NULL U THEN RETURN T
ELSE IF NOT !*EVAL CAR U THEN RETURN NIL;
U := CDR U;
GO TO A
END;
SYMBOLIC PROCEDURE APPEND(U,V);
IF NULL U THEN V ELSE CAR U . APPEND(CDR U,V);
SYMBOLIC PROCEDURE !*APPLY(U,V);
!*EVAL(U . MAPCAR(V,FUNCTION MKQUOTE));
SYMBOLIC PROCEDURE MKQUOTE U;
LIST('QUOTE,U);
SYMBOLIC PROCEDURE ASSOC(U,V);
IF NULL V THEN NIL
ELSE IF U=CAAR V THEN CAR V
ELSE ASSOC(U,CDR V);
SYMBOLIC PROCEDURE CAAAAR(X);
CAR CAR CAR CAR X;
SYMBOLIC PROCEDURE CAAADR(X);
CAR CAR CAR CDR X;
SYMBOLIC PROCEDURE CAAAR(X);
CAR CAR CAR X;
SYMBOLIC PROCEDURE CAADAR(X);
CAR CAR CDR CAR X;
SYMBOLIC PROCEDURE CAADDR(X);
CAR CAR CDR CDR X;
SYMBOLIC PROCEDURE CAADR(X);
CAR CAR CDR X;
SYMBOLIC PROCEDURE CAAR(X);
CAR CAR X;
SYMBOLIC PROCEDURE CADAAR(X);
CAR CDR CAR CAR X;
SYMBOLIC PROCEDURE CADADR(X);
CAR CDR CAR CDR X;
22
SYMBOLIC PROCEDURE CADAR(X);
CAR CDR CAR X;
SYMBOLIC PROCEDURE CADDAR(X);
CAR CDR CDR CAR X;
SYMBOLIC PROCEDURE CADDDR(X);
CAR CDR CDR CDR X;
SYMBOLIC PROCEDURE CADDR(X);
CAR CDR CDR X;
SYMBOLIC PROCEDURE CADR(X);
CAR CDR X;
SYMBOLIC PROCEDURE CDAAAR(X);
CDR CAR CAR CAR X;
SYMBOLIC PROCEDURE CDAADR(X);
CDR CAR CAR CDR X;
SYMBOLIC PROCEDURE CDAAR(X);
CDR CAR CAR X;
SYMBOLIC PROCEDURE CDADAR(X);
CDR CAR CDR CAR X;
SYMBOLIC PROCEDURE CDADDR(X);
CDR CAR CDR CDR X;
SYMBOLIC PROCEDURE CDADR(X);
CDR CAR CDR X;
SYMBOLIC PROCEDURE CDAR(X);
CDR CAR X;
SYMBOLIC PROCEDURE CDDAAR(X);
CDR CDR CAR CAR X;
SYMBOLIC PROCEDURE CDDADR(X);
CDR CDR CAR CDR X;
SYMBOLIC PROCEDURE CDDAR(X);
CDR CDR CAR X;
SYMBOLIC PROCEDURE CDDDAR(X);
CDR CDR CDR CAR X;
SYMBOLIC PROCEDURE CDDDDR(X);
CDR CDR CDR CDR X;
SYMBOLIC PROCEDURE CDDDR(X);
CDR CDR CDR X;
23
SYMBOLIC PROCEDURE CDDR(X);
CDR CDR X;
SYMBOLIC PROCEDURE DEFLIST(U,V);
BEGIN SCALAR X;
A: IF NULL U THEN RETURN REVERSE X;
PUT (CAAR U,V,CADAR U);
X := CAAR U . X;
U := CDR U;
GO TO A
END;
SYMBOLIC PROCEDURE DELETE(U,V);
IF NULL V THEN NIL
ELSE IF U=CAR V THEN CDR V
ELSE CAR V . DELETE(U,CDR V);
SYMBOLIC PROCEDURE DIVIDE(M,N);
(M/N) . REMAINDER(M,N);
SYMBOLIC PROCEDURE X=Y;
IF ATOM X THEN IF NUMBERP X THEN NUMBERP Y AND X EQN Y
ELSE X EQ Y
ELSE CAR X=CAR Y AND CDR X=CDR Y;
SYMBOLIC PROCEDURE M>=N;
M=N OR M>N;
SYMBOLIC PROCEDURE M>N;
NOT (M<=N);
SYMBOLIC PROCEDURE LENGTH U;
IF NULL U THEN 0 ELSE LENGTH CDR U+1;
SYMBOLIC PROCEDURE M<=N;
NOT(M>N);
FEXPR PROCEDURE LIST U;
%Returns a list of elements in U;
SYMBOLIC PROCEDURE MAP(U,!*PI!*);
BEGIN
A: IF NULL U THEN RETURN NIL;
!*PI!* U;
U := CDR U;
GO TO A;
END;
SYMBOLIC PROCEDURE MAPC(X,!*PI!*);
BEGIN
A: IF NULL X THEN RETURN;
!*PI!* CAR X;
X := CDR X;
GO TO A
24
END;
SYMBOLIC PROCEDURE MAPCAR(X,!*PI!*);
IF NULL X THEN NIL
ELSE !*PI!* CAR X . MAPCAR(CDR X,!*PI!*);
SYMBOLIC PROCEDURE MAPCON(X,!*PI!*);
IF NULL X THEN NIL
ELSE NCONC(!*PI!* X,MAPCON(CDR X,!*PI!*));
SYMBOLIC PROCEDURE MAPLIST(X,!*PI!*);
IF NULL X THEN NIL
ELSE !*PI!* X . MAPLIST(CDR X,!*PI!*);
SYMBOLIC PROCEDURE MEMBER(X,Y);
IF NULL Y THEN NIL
ELSE IF X=CAR Y THEN T
ELSE MEMBER(X,CDR Y);
SYMBOLIC PROCEDURE M-N;
M+(-N);
SYMBOLIC PROCEDURE NCONC(U,V);
BEGIN SCALAR W;
IF NULL U THEN RETURN V;
W := U;
A: IF NULL CDR W THEN GO TO B;
W := CDR W;
GO TO A;
B: RPLACD(W,V);
RETURN U
END;
SYMBOLIC PROCEDURE NOT U;
U EQ NIL;
SYMBOLIC PROCEDURE NULL U;
U EQ NIL;
FEXPR PROCEDURE OR(U);
BEGIN
A: IF NULL U THEN RETURN NIL
ELSE IF !*EVAL CAR U THEN RETURN T;
U := CDR U;
GO TO A
END;
SYMBOLIC PROCEDURE PAIR(U,V);
BEGIN SCALAR X,Y,Z;
X := U;
Y := V;
A: IF NULL X THEN IF NULL Y THEN RETURN Z
ELSE ERROR LIST('PAIR,U,V);
IF NULL Y THEN ERROR LIST('PAIR,U,V);
25
Z := (CAR U . CAR V) . Z;
X := CDR X;
Y := CDR Y;
GO TO A
END;
SYMBOLIC PROCEDURE PRIN0 U;
IF ATOM U THEN PRIN1 U
ELSE BEGIN SCALAR V;
V := U;
PRINC "(";
A: PRIN0 CAR V;
IF NULL CDR V THEN GO TO C
ELSE IF ATOM CDR V THEN GO TO B;
PRINC " ";
V := CDR V;
GO TO A;
B: PRINC " . ";
PRIN0 CDR V;
C: PRINC ")";
RETURN U
END;
SYMBOLIC PROCEDURE PRINT U;
BEGIN PRIN0 U; TERPRI(); RETURN U END;
SYMBOLIC PROCEDURE PROG2(U,V);
V;
FEXPR PROCEDURE QUOTE U;
CAR U;
SYMBOLIC PROCEDURE READ();
%Reads one S-expression from input;
SYMBOLIC PROCEDURE REVERSE(X);
BEGIN SCALAR U,V;
V := X;
A: IF NULL V THEN RETURN U;
U := CAR V . U;
V := CDR V;
GO TO A;
END;
SYMBOLIC PROCEDURE SASSOC(U,V,!*PI!*);
IF NULL V THEN !*PI!*()
ELSE IF U=CAAR V THEN CAR V
ELSE SASSOC(U,CDR V,!*PI!*);
SYMBOLIC PROCEDURE SUBLIS(X,Y);
BEGIN SCALAR U;
IF NULL X THEN RETURN Y;
U := X;
A: IF NULL U THEN RETURN IF ATOM Y
26
OR (U := SUBLIS(X,CAR Y) . SUBLIS(X,CDR Y)) = Y
THEN Y
ELSE U
ELSE IF Y = CAAR U THEN RETURN CDAR U;
U := CDR U;
GO TO A
END;
SYMBOLIC PROCEDURE SUBST(U,V,W);
IF NULL W THEN NIL
ELSE IF V=W THEN U
ELSE IF ATOM W THEN W
ELSE SUBST(U,V,CAR W).SUBST(U,V,CDR W);
27
4. FORMAL SYNTAX DEFINITION OF REDUCE
The following is a definition of the syntax of a subset of
REDUCE, due to R. Loos [4]. A more complete specification is under
development.
Meta notation: Terminals are headed by a quote mark
< > denotes optionality
( )* denotes 0 or more repetitions
/ or ( / ) denotes alternatives
r-def: (type 'PROCEDURE id < '( (id ', )* ') > ';
/ id '( (id ', )* ') ':= ) r-expr
type: 'LISP / 'SYMBOLIC / 'INTEGER / 'MACRO / 'FEXPR
id: alphabetic / id (alphabetic/digit)*
r-expr: id ':= r-expr / disjunction
disjunction: conjunction / disjunction 'OR conjunction
conjunction: negation / conjunction 'AND negation
negation: relation / 'NOT negation
relation: term / term rel-op term
term: factor / term plus-op factor
factor: neg-pow / factor tim-op neg-pow
neg-pow: <'+ / '- > pow
pow: dot-expr / pow '** dot-expr
dot-expr: primary / primary '. dot-expr
primary: constant / id / fn-call /'( r-expr ') /
'BEGIN (decl '; )* <label-stat ('; label-stat)*> <'; > 'END /
'IF r-expr 'THEN r-expr <'ELSE r-expr>
constant: integer / 'NIL / 'T / '' s-expr
integer: digit (digit)*
s-expr: id / <'-> integer / '( s-expr (s-expr)* <'. sexpr> ')
fn-call: id '( <r-expr (', r-expr)*> ') / id r-expr
decl: ('INTEGER / 'SCALAR ) id (', id)*
label-stat: (id ': )* block-stat
28
block-stat: 'RETURN r-expr / ('GO 'TO /'GOTO ) id /
'IF r-expr 'THEN block-stat <'ELSE block-stat> / r-expr
tim-op: '* / '/
plus-op: '+ / '-
rel-op: '< / '<= / '= / 'NEQ / 'EQ / '>= / '> / 'MEMBER
29
REFERENCES
[1] HEARN, A. C., REDUCE 2 User's Manual, Utah Computational Physics
Group Memo No UCP-19, March 1973.
[2] McCARTHY J., ABRAHAMS, P. W., EDWARDS. J., HART, T. P. and
LEVIN, M. I., LISP 1.5 Programmer's Manual, M.I.T. Press, 1965
[3] WEISSMAN, Clark, LISP 1.5 Primer, Dickenson, 1967
[4] LOOS, R. G. K., Private Communication.
30
2.18 SOS-Link
Facilities are present in REDUCE to allow users editing
access to program source files during calculations. To use these
facilities, all function definitions should be input from SOS files,
and global changes to these files, such as renumbering and insertion
of page marks, should be avoided.
There are two ways in which this link may be used. These are
as follows:
2.18.1 Correction of Input Errors
If an error is encountered on input while an SOS file is
being loaded, the system will print the error diagnostics, and then
print the message EDIT?. If the user types Y (for yes), the system
will then load SOS and print the line which marks the beginning of
the command in which the error occurred. The error can now be
corrected. After editing is complete, typing G (for go) in SOS has
the effect of closing the file, reloading your REDUCE core image, and
rereading the input file from the beginning of the command where the
error occurred.
2.18.2 Editing Function Definitions
Any functions which were input to REDUCE from an SOS file
have information saved with them which tells the system where they
occur in the file (this is why global changes to the source files
should be avoided). If the user desires to change the function
definition during an REDUCE calculation, he can access the source
definition in the file by typing
EDIT <function name>;
This command causes SOS to be loaded and the first line of the
function printed. The user can now edit the function definition.
Typing G will cause the user's REDUCE program to be reloaded, and the
altered function definition to be read from the file. Note, however,
that only one function may be redefined at a time by this method.
2.19 Debugging Facilities in REDUCE
A few simple debugging facilities are available in REDUCE for
the more experienced programmer. These are as follows:
2.19.1 Tracing Functions
A command TR is available in REDUCE for tracing LISP function
calls. This command, and the associated commands UNTR, TRST and
UNTRST, are used in the form:
31
TR <function name>,<function name>,...,<function name>;
TR calls the LISP function TRACE, and its output is in exactly the
same form. The trace may be turned off by the function UNTR which
uses the LISP function UNTRACE.
WARNING:
Because LISP establishes fast links to functions in compiled
code once that code has been referenced, it is necessary to inhibit
this when tracing is required. TR does this as part of its
evaluation sequence, but if tracing is not required until late in a
program, the fast links already established by then may nullify the
trace. To prevent this, TR should be called with no arguments as the
first command in the program.
2.19.2 Tracing Assignments in Compound Statements
Useful diagnostic information can often be obtained by
observing the values which variables acquire during assignments in
particular functions. To do this in REDUCE, one uses the command
TRST. There are some restrictions on the function names which appear
in the arguments of this function, however. First, the functions must
obviously be in the system in symbolic form; compiled functions no
longer contain information on the assignment variable names.
Secondly, the functions must have a compound statement at their top
level.
This particular trace may be turned off by the command
UNTRST.
32
3. RUNNING REDUCE SYMBOLIC MODE ON THE STANFORD PDP-10
3.1 A symbolic mode version of REDUCE is stored as a 24K system
with filename RLISP.DMP.
REDUCE may be loaded by typing R RLISP. A message will then
inform you when the program is loaded. The system then expects REDUCE
commands from you. You can return to LISP by the command END;
If you require more core for your job, you can get it by
typing
↑C
.CORE <size required><cr>
.ST<cr>
You will then be back in REDUCE.
Alternatively, you can load the program initially with a larger core
size by typing
.R RLISP <core size><cr>
3.2 Special Features
3.2.1 If you give IN a variable or dotted pair as argument, the
system expects to find the file in your disk area, and similarly with
OUT. In addition, the reserved identifier L is used to represent the
line printer on output.
i. e. OUT L;
sends output to the line printer.
Input from other devices may be specified by preceding the
file name by the device name. For example, to input a file ANDY from
disk area [S,JAM] followed by FOO from DTA2:, you would type
IN (S,JAM),ANDY,DTA2!:,FOO;
3.2.2 The altmode character may be used as a terminator. This is very
convenient, as it is not then necessary to follow it by a carriage
return as is required with the other terminators. However, the value
of the symbolic evaluation is not printed in this case.
3.2.3 NOT
The character ¬ may be used interchangably with the unary
function NOT on input. On output, however, NOT is printed.
3.3 A SAMPLE PROGRAM
33
.R RLISP load the program
REDUCE 2 <system date>... system loaded
*COMMENT A SAMPLE PROGRAM; comments are allowed
*CAR ('(A)); compute the CAR of (A)
A here's its value
*ASSOC(U,V):=IF NULL V THEN NIL now define ASSOC
* ELSE IF U≡ CAAR V THEN CAR V
* ELSE ASSOC(U,CDR V);
*** ASSOC REDEFINED diagnostic message from REDUCE
ASSOC value from definition of ASSOC
*ASSOC ('A,'((B . C) (A . D))); test ASSOC
(A . D) it works!
*END; return to LISP
*** value of END routine
ENTERING LISP... so that you know
*